package cm.unit4.theme4;

import cm.commom.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;

public class SerializeAndDeserializeBinTree {

    int index = -1;
    /**
     * 分别遍历左节点和右节点，空使用#代替，节点之间，隔开
     */
    public String Serialize01(TreeNode root) {
        if (root == null) {
            return "#";
        } else {
            return root.val + "," + Serialize01(root.left) + "," + Serialize01(root.right);
        }
    }
    /**
     * 使用index来设置树节点的val值，递归遍历左节点和右节点，如果值是#则表示是空节点，直接返回
     */
    TreeNode Deserialize01(String str) {
        String[] s = str.split(",");//将序列化之后的序列用，分隔符转化为数组
        index++;//索引每次加一
        int len = s.length;
        if (index > len) {
            return null;
        }
        TreeNode treeNode = null;
        if (!s[index].equals("#")) {//不是叶子节点 继续走 是叶子节点出递归
            treeNode = new TreeNode(Integer.parseInt(s[index]));
            treeNode.left = Deserialize01(str);
            treeNode.right = Deserialize01(str);
        }
        return treeNode;
    }

    String Serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }

        Queue<TreeNode> queue = new ArrayDeque<>(100);
        StringBuilder builder = new StringBuilder();

        // queue的值不能为null

        queue.add(root);
        builder.append(root.val);

        TreeNode node;
        while (!queue.isEmpty()) {
            node = queue.remove();

            // 持久化
            if (node.left != null) {
                builder.append("!").append(node.left.val);
                queue.add(node.left);
            }else {
                builder.append("!#");
            }

            if (node.right != null) {
                builder.append("!").append(node.right.val);
                queue.add(node.right);
            }else {
                builder.append("!#");
            }
        }
        return new String(builder);
    }

    TreeNode Deserialize(String str) {
        if (str==null || str.length()==0 || "#".equals(str)){
            return null;
        }

        Queue<TreeNode> queue = new ArrayDeque<>(100);
        String[] strings = str.split("!");
        TreeNode root = new TreeNode(Integer.parseInt(strings[0]));
        queue.add(root);

        TreeNode node;
        int index = 1;
        while (!queue.isEmpty() && index<strings.length){
            node = queue.remove();

            if (!"#".equals(strings[index])){
                TreeNode leftNode = new TreeNode(Integer.parseInt(strings[index++]));
                node.left = leftNode;
                queue.add(leftNode);
            }else {
                index++;
            }

            if (!"#".equals(strings[index])){
                TreeNode rightNode = new TreeNode(Integer.parseInt(strings[index++]));
                node.right = rightNode;
                queue.add(rightNode);
            }else {
                index++;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.buildDemoTree();
        System.out.println("tree->"+root);

        SerializeAndDeserializeBinTree obj = new SerializeAndDeserializeBinTree();
        String serialize = obj.Serialize(root);
        System.out.println(serialize);

        TreeNode treeNode = obj.Deserialize(serialize);
        System.out.println(treeNode);
    }
}
